
\subsection{Trie}

先考虑怎么存多个串

一种树，每个结点有 $|∑|$ 个儿子，每条边表示一个字符

空间 $O(len)$ （如果假设 $|∑|$ 为常数）

要判断某个串是否等于某个模式串，只要在 Trie 上走一遍（线性的）

\subsection{在 Trie 上 KMP}

实际上要做的事情是求出 Trie 的每个节点的 $next$ 值

当然，这里的 $next$ 不再是一个值，而是相当于是一个指针 —— 它可能指向其他分支的节点。

这时 $next$ 的定义：最长的等于同长度的后缀的从根开始的路径的长度

求法跟  KMP  中的一样，只是要改成在 Trie 上  BFS 

复杂度：均摊分析失效了，其实只能在每条链上均摊分析，于是总复杂度为模式串长总和
